// https://www.lintcode.com/problem/movie-recommendation/

public class Solution {
    public List<List<Integer>> minMalwareSpread(List<List<Integer>> graph) {
        List<List<Integer>> ret = new ArrayList<>();
        HashMap<Integer, HashSet<Integer>> movieViewedBy = new HashMap<>();
        for (int i = 0; i < graph.size(); ++i) {
            List<Integer> movies = graph.get(i);
            for (Integer m : movies) {
                if (!movieViewedBy.containsKey(m)) {
                    movieViewedBy.put(m, new HashSet<>());
                }
                movieViewedBy.get(m).add(i);
            }
        }
        HashMap<Integer, HashMap<Integer, Integer>> candidates = new HashMap<>();
        for (int i = 0; i < graph.size(); ++i) {
            candidates.put(i, new HashMap<>());
            for (Integer m : graph.get(i)) {
                for (Integer u : movieViewedBy.get(m)) {
                    if (i != u) {
                        for (Integer _m : graph.get(u)) {
                            if (!graph.get(i).contains(_m)) {
                                if (!candidates.get(i).containsKey(_m)) {
                                    candidates.get(i).put(_m, 0);
                                }
                                Integer plus_one = candidates.get(i).get(_m) + 1;
                                candidates.get(i).put(_m, plus_one);
                            }
                        }
                    }
                }
            }
            // 排序
            class MapValueComparator implements Comparator<Map.Entry<Integer, Integer>> {
                @Override
                public int compare(Map.Entry<Integer, Integer> me1, Map.Entry<Integer, Integer> me2) {
                    if (me1.getValue() < me2.getValue()) {
                        return 1;
                    } else if (me1.getValue() == me2.getValue()) {
                        if (me1.getKey() < me2.getKey()) {
                            return -1;
                        } else if (me1.getKey() == me2.getKey()) {
                            return 0;
                        } else {
                            return 1;
                        }
                    } else {
                        return -1;
                    }
                }
            }
            HashMap<Integer, Integer> values = candidates.get(i);
            List<Map.Entry<Integer,Integer>> list = new ArrayList<>(values.entrySet());
            Collections.sort(list,new MapValueComparator());
            ret.add(new ArrayList<>());
            for (int j = 0; j < list.size(); ++j) {
                if (j < 5) {
                    ret.get(ret.size() - 1).add(list.get(j).getKey());
                } else {
                    break;
                }
            }
        }
        return ret;
    }
}